Aitken's delta-squared process

In numerical analysis, Aitken's delta-squared process is a series acceleration method, used for accelerating the rate of convergence of a sequence. It is named after Alexander Aitken, who introduced this method in 1926^[1]. Its early form was known to Seki Kōwa (end of 17th century) and was found for rectification of the circle, i.e. the calculation of π. It is most useful for accelerating the convergence of a sequence that is converging linearly.

1 Definition
2 Properties
3 Example calculations
4 See also
5 Notes
6 References

Definition

Given a sequence $x={(x_n)}_{n\in\N}$ , one associates to this sequence the new sequence

$Ax={\left(\frac{x_{n%2B2}\,x_n-(x_{n%2B1})^2}{x_{n%2B2}-2\,x_{n%2B1}%2Bx_n}\right)}_{n\in\Z^*},$

which can also be written as

$Ax_n=x_n-\frac{(\Delta x_n)^2}{\Delta^2 x_n},$

where

$\Delta x_{n}={(x_{n%2B1}-x_{n})},\$

and

$\Delta^2 x_n=x_n -2x_{n%2B1} %2B x_{n%2B2},\$

for $n = 0, 1, 2, 3, \dots \,$

(To use this nice operator notation, one has to allow for the indices to start from n = 2 on, or apply a translation operator which first shifts the sequence indices by two, or to adopt the convention that x_n = 0 for all n < 0.)

Obviously, Ax is ill-defined if Δ²x contains a zero element, or equivalently, if the sequence of first differences has a repeating term. From a theoretical point of view, assuming that this occurs only for a finite number of indices, one could easily agree to consider the sequence Ax restricted to indices n>n₀ with a sufficiently large n₀. From a practical point of view, one does in general rather consider only the first few terms of the sequence, which usually provide the needed precision. Moreover, when numerically computing the sequence, one has to take care to stop the computation when rounding errors become too important in the denominator, where the Δ² operation may cancel too many significant digits.

Properties

Aitken's delta-squared process is a method of acceleration of convergence, and a particular case of a nonlinear sequence transformation.

$x$ will converge linearly to $\ell$ if there exists a number μ ∈ (0, 1) such that

$\lim_{n\to \infty} \frac{|x_{n%2B1}-\ell|}{|x_n-\ell|} = \mu.$

Aitken's method will accelerate the sequence $x_n$ if $\lim_{n \to \infty}\frac{A_n-\ell}{x_n-\ell}=0.$

$A$ is not a linear operator, but a constant term drops out, viz: $A[x-\ell] = Ax - \ell$ , if $\ell$ is a constant. This is clear from the expression of $Ax$ in terms of the finite difference operator $\Delta$ .

Although the new process does not in general converge quadratically, it can be shown that for a fixed point process, that is, for an iterated function sequence $x_{n%2B1}=f(x_n)$ for some function $f$ , converging to a fixed point, the convergence is quadratic. In this case, the technique is known as Steffensen's method.

Empirically, the A-operation eliminates the "most important error term". One can check this by considering a sequence of the form $x_n=\ell%2Ba^n%2Bb^n$ , where $0<b<a<1$ : The sequence $Ax$ will then go to the limit like $b^n$ goes to zero.

One can also show that if $x$ goes to its limit $\ell$ at a rate strictly greater than 1, $Ax$ does not have a better rate of convergence. (In practice, one rarely has e.g. quadratic convergence which would mean over 30 resp. 100 correct decimal places after 5 resp. 7 iterations (starting with 1 correct digit); usually no acceleration is needed in that case.)

In practice, $Ax$ converges much faster to the limit than $x$ does, as demonstrated by the example calculations below. Usually, it is much cheaper to calculate $Ax$ (involving only calculation of differences, one multiplication and one division) than to calculate many more terms of the sequence $x$ . Care must be taken, however, to avoid introducing errors due to insufficient precision when calculating the differences in the numerator and denominator of the expression.

Example calculations

The value of $\sqrt{2} \approx 1.4142136$ may be approximated by assuming an initial value for $a_n$ and iterating the following:

$a_{n%2B1} = \frac{a_n %2B \frac{2}{a_n}}{2}.$

Starting with $a_0 = 1:$

n	x = iterated value	Ax
0	1	1.4285714
1	1.5	1.4141414
2	1.4166667	1.4142136
3	1.4142157	--
4	1.4142136	--

The value of $\frac{\pi}{4}$ may be calculated as an infinite sum:

$\frac{\pi}{4} = \sum_{n=0}^\infty \frac{(-1)^n}{2n%2B1} \approx 0.785398$

n	term	x = partial sum	Ax
0	1	1	0.79166667
1	−0.33333333	0.66666667	0.78333333
2	0.2	0.86666667	0.78630952
3	−0.14285714	0.72380952	0.78492063
4	0.11111111	0.83492063	0.78567821
5	−9.0909091×10⁻²	0.74401154	0.78522034
6	7.6923077×10⁻²	0.82093462	0.78551795
7	-6.6666667×10⁻²	0.75426795	--
8	5.8823529×10⁻²	0.81309148	--

Notes

^ Alexander Aitken, "On Bernoulli's numerical solution of algebraic equations", Proceedings of the Royal Society of Edinburgh (1926) 46 pp. 289–305.

References

William H. Press, et al., Numerical Recipes in C, (1987) Cambridge University Press, ISBN 0-521-43108-5 (See section 5.1)
Abramowitz and Stegun, Handbook of Mathematical Functions, section 3.9.7